package divide_and_conquer;

import java.util.HashMap;

//https://leetcode.cn/leetbook/read/illustration-of-algorithm/99lxci/
//某二叉树的先序遍历结果记录于整数数组 preorder，它的中序遍历结果记录于整数数组 inorder。
// 请根据 preorder 和 inorder 的提示构造出这棵二叉树并返回其根节点。
public class LCR_124推理二叉树 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    class Solution {
        int[] preorder;
        HashMap<Integer, Integer> hmap = new HashMap<>();
        public TreeNode deduceTree(int[] preorder, int[] inorder) {
            this.preorder = preorder;
            for(int i = 0; i < inorder.length; i++)
                hmap.put(inorder[i], i);
            return recur(0, 0, inorder.length - 1);
            // 根节点在前序遍历的索引 root 、子树在中序遍历的左边界 left 、子树在中序遍历的右边界 right ；
        }
        TreeNode recur(int root, int left, int right) {
            if(left > right) return null;                          // 递归终止
            TreeNode node = new TreeNode(preorder[root]);          // 建立根节点
            int i = hmap.get(preorder[root]);                      // 划分根节点、左子树、右子树   查找根节点在中序遍历 inorder 中的索引 i
            node.left = recur(root + 1, left, i - 1);              // 开启左子树递归
            node.right = recur(root + i - left + 1, i + 1, right); // 开启右子树递归  根节点索引 + 左子树长度 + 1
            return node;                                           // 回溯返回根节点
        }
    }
}
